#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    Node* connect(Node* root)
    {
        if (root == nullptr)
            return nullptr;
        queue<Node*> q;
        q.push(root);
        while (!q.empty())
        {
            int len = q.size();
            for (int i = 0; i < len; ++i)
            {
                Node* cur = q.front();
                q.pop();
                if (i < len - 1)
                {
                    cur->next = q.front();
                }
                if (cur->left != nullptr)
                    q.push(cur->left);
                if (cur->right != nullptr)
                    q.push(cur->right);
            }
        }
        return root;
    }
};

class Solution {
public:
    Node* connect(Node* root)
    {
        Node* cur = root;
        while (cur != nullptr)
        {
            Node* dummyNode = new Node(-1);
            Node* prev = dummyNode;
            Node* curr = cur;
            while (curr != nullptr)
            {
                if (curr->left != nullptr)
                {
                    prev->next = curr->left;
                    prev = prev->next;
                }
                if (curr->right != nullptr)
                {
                    prev->next = curr->right;
                    prev = prev->next;
                }
                curr = curr->next;
            }
            cur = dummyNode->next;
        }
        return root;
    }
};

